package com.hanxiaozhang.no10leetcode.array;

import java.util.*;

/**
 * 〈一句话功能简述〉<br>
 * 〈〉
 * <p>
 * 给定一个没有重复数字的候选数组和一个目标值，找出数组中数字之和为目标值的组合。同一个数字被选择的次数没有限制。
 * 注意：所有数字均为正整数，答案中不包含重复的组合
 * 示例1:
 * 输入: arr = [2,3,6,7], target = 7
 * 输出: [ [7], [2,2,3] ]
 * 示例2:
 * 输入: arr = [2,3,5], target = 8,
 * 输出: [ [2,2,2,2], [2,3,3], [3,5] ]
 * <p>
 * 思路：(回溯：背一下吧，第一次遇见这个种题)
 * 1. 数组排序：将数组排序，可以推论出：如果 sum > target 或 sum = target时， sum + next元素 > target 一定成立，所以可以结束循环。
 * 2. 回溯：递归调用 -> 递归前添加元素，递归后要恢复现场删除元素
 *
 * @author hanxinghua
 * @create 2024/1/12
 * @since 1.0.0
 */
public class No39CombinationSum {


    public static void main(String[] args) {

        int[] arr = {2, 3, 6, 7};
        int target = 8;

        List<List<Integer>> lists = combinationSum(arr, target);
        System.out.println(lists);
    }


    public static List<List<Integer>> combinationSum(int[] arr, int target) {
        List<List<Integer>> res = new ArrayList<>();
        Arrays.sort(arr);
        backTrack(0, arr, new ArrayList<>(), res, target, 0);
        return res;
    }

    /**
     * @param sum      相加和
     * @param arr      数组
     * @param currList 当前数组
     * @param res      结果集合
     * @param target   目标数
     * @param start    开始位置
     * @return 1代表 sum > target ; 0代表 sum == target; -1代表继续回溯
     */
    private static int backTrack(int sum, int[] arr, List<Integer> currList, List<List<Integer>> res, int target, int start) {
        if (sum > target) {
            return 1;
        }
        if (sum == target) {
            res.add(new ArrayList<>(currList));
            return 0;
        } else {
            for (int i = start; i < arr.length; i++) {
                // 将当前位置元素添加currList
                currList.add(arr[i]);
                // 将当前元素添加后情况，递归调用
                int sumResult = backTrack(sum + arr[i], arr, currList, res, target, i);
                // 恢复现场
                currList.remove(currList.size() - 1);
                // 数组已经排序，如果 sum > target 或 sum = target 意味着 sum + next元素 > target，所以可以在这里打破循环。
                if (sumResult != -1) {
                    break;
                }
            }
        }
        return -1;
    }


}
